<?php 
set_time_limit(0);

/*$hashMap = new HashMap();
		//$hashMap->setSize($j);
		$fileName = '1000.txt';
		$file = fopen($fileName, 'r');
		while (!feof($file)) {
			$key = fgets($file);
			$hashMap->insertKey((int)$key);
		}
fclose($file);

var_dump($hashMap->getCounts());

$maxSlotSize = 0;
for ($j = 1000; $j < 260000; $j += 5000) {
	// $test = fopen('maxSlot_' . $j . '.txt', 'w+');
	for ($i = 0; $i < 100; $i++) {
		$hashMap = new HashMap();
		$hashMap->setSize($j);
		$fileName = '1000.txt';
		$file = fopen($fileName, 'r');
		while (!feof($file)) {
			$key = fgets($file);
			$hashMap->insertKey((int)$key);
		}
		fclose($file);
		
		$hashMap->getCounts();
		if ($maxSlotSize < $hashMap->getMaxSlotSize()) {
			$maxSlotSize = $hashMap->getMaxSlotSize();
		}
	}
}*/

class HashMap {
	private $hashTable;
	private $m;				/* Size of the single hash table, e.g. number of buckets */
	private $p;				/* Prime number greater than any key value (1..1000) chosen arbitrarily */
	
	/* So-called globals */
	private $a;				
	private $b;
	private $rehashCount;
	private $collisionCount;
	private $maxSlotSize;
	
	public function __construct() {
		$this->m = 10000;
		$this->p = 1000003;	/* @FIXME: it has to be next prime largen than the any key value !!!!! */
		$this->a = mt_rand(1, $this->p-1);
		$this->b = mt_rand(0, $this->p-1);
		$this->rehashCount = 0;
		$this->collisionCount = 0;
		$this->maxSlotSize = 0;
	}
	
	public function setSize($m) {
		$this->m = $m;
	}
	
	public function getSize() {
		
		return $this->m;
	}
	
	public function getCollisionCount() {
		
		return $this->collisionCount;
	}
	
	public function getMaxSlotSize()
	{
		return $this->maxSlotSize;
	}	
	public function insertKey($x) {
		$level1Position = $this->generateHash($x);
		if (isset($this->hashTable[$level1Position])) {
			
			$this->collisionCount += 1;

			if ($this->isDuplicate($level1Position, $x)) {
				echo 'Key already exists. Do nothing... <br>';
				return;
			}
			
			$size = count($this->hashTable[$level1Position]['hashTable']);
			$a = $this->hashTable[$level1Position]['a'];
			$b = $this->hashTable[$level1Position]['b'];
			$m = pow(($size + 1), 2);
			$p = $this->getNextPrime($m);
			
			$level2Position = $this->generateHash($x, $a, $b, $m, $p);

			if (
				isset($this->hashTable[$level1Position]['hashTable'][$level2Position])
			) {
				$this->rehashTable($level1Position, $x);
			} else {
				$this->hashTable[$level1Position]['m'] = $m;
				$this->hashTable[$level1Position]['p'] = $p;
				$this->hashTable[$level1Position]['hashTable'][$level2Position] = $x;
			}
		} else {
			/* a and b specific to the level 2 hash table */
			$m = 1;
			$p = $this->getNextPrime($m);
			list($a, $b) = $this->generateConstants($p);
			
			$level2Position = $this->generateHash($x, $a, $b, $m, $p);
			$this->hashTable[$level1Position] = array (
				'a' => $a,
				'b' => $b,
				'm' => $m,
				'hashTable' => array()
			);
			$this->hashTable[$level1Position]['hashTable'][$level2Position] = $x;
			
			//$this->hashTable[$level1Position] = $x;
		}
		
	}
	
	public function isDuplicate($level1Position, $x) {
		$size = count($this->hashTable[$level1Position]['hashTable']);
		$a = $this->hashTable[$level1Position]['a'];
		$b = $this->hashTable[$level1Position]['b'];
		$level2Position = $this->generateHash($x, $a, $b, $size);
		
		if (
			isset($this->hashTable[$level1Position]['hashTable'][$level2Position]) &&
			$this->hashTable[$level1Position]['hashTable'][$level2Position] == $x
		) {
			return true;
		}
		
		return false;
	}
	
	public function rehashTable($level1Position, $x) {
		//echo 'rehashing<br>';
		$prevHashTable = $this->hashTable[$level1Position]['hashTable'];
		$size = count($prevHashTable);
		$a = $this->hashTable[$level1Position]['a'];
		$b = $this->hashTable[$level1Position]['b'];
		$m = pow(($size + 1), 2);
		$hashTable = array();
		
		$rehashed = false;
		
		$retries = 0;
		$prevHashTable[] = $x;
		
		while (!$rehashed) {
			
			$rehashed = true;
			
			if ($retries > 200) {
				echo 'Too many tries';
				die();
			}
			list($a, $b) = $this->generateConstants();		// Trying new a and b until there is no collisions
			foreach ($prevHashTable as $value) {
				$level2Position = $this->generateHash($value, $a, $b, $m);
				if (isset($hashTable[$level2Position])) {
					$rehashed = false;
					$hashTable = array();
					break;
				} else {
					$hashTable[$level2Position] = $value;
				}
			}
		
			$retries++;
		}
		
		$this->hashTable[$level1Position] = array (
			'a' => $a,
			'b' => $b,
			'm' => $m,
			'hashTable' => $hashTable
		);
		
		$this->rehashCount++;
	}
	
	public function getNextPrime($value) {
		$isPrime = false;
		$prime = $this->p;
		for ($i = $value + 1; $i < 2 * $value; $i++) {
			if ($this->isPrime($i)) {
				$prime = $i;
				break;
			}
		}
		
		return $prime;
	}
	
	public function isPrime($value) {
		for ($i = 2; $i < $value; $i++) {
			if ($value % $i == 0) {
				return false;
			}
		}
		
		return true;
	}
	
	public function generateHash($x, $a = null, $b = null, $m = null, $p = null) {
		if ($a == null && $b == null && $m == null && $p == null) {
			$a = $this->a;
			$b = $this->b;
			$m = $this->m;
		}
		
		//echo 'Val: ' . $x . ' a: ' . $a . ' $b: ' . $b . ' m: ' . $m . '<br>';
		//echo 'fmod($a * $x + $b, $this->p)' . fmod($a * $x + $b, $this->p) . '<br>';
		//echo 'fmod(fmod($a * $x + $b, $this->p), $m)' . fmod(fmod($a * $x + $b, $this->p), $m) . '<br>';
		$result = fmod(fmod($a * $x + $b, $this->p), $m);

		return $result;
	}
	
	public function generateConstants() {
		
		return array(mt_rand(1, $this->p - 1), mt_rand(0, $this->p - 1));
	}
	
	public function getHashTable() {
		
		return $this->hashTable;
	}
	
	public function getHashTableSize() {
		$count = 0;
		foreach ($this->hashTable as $level1Position => $elements) {
			$count += count($elements['hashTable']);
		}
		
		return $count;
	}
	
	public function getCounts() {
		$counts = array();
		$count = 0;
		foreach ($this->hashTable as $level1Position => $elements) {
			$count =  count($elements['hashTable']);
			
			if ($count > $this->maxSlotSize) {
				$this->maxSlotSize = $count;
			}
			
			if (isset($counts[$count])) {
				$counts[$count] += 1;
			} else {
				$counts[$count] = 1;
			}
		}
		
		
		return $counts;
	}
}

